package com.wc.算法提高课.E第五章_数学知识.博弈论.取石子游戏;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/10/6 22:24
 * @description https://www.acwing.com/problem/content/description/1324/
 */
public class Main {
    /**
     * 思路：<p>
     * 定义一个l[i][j] = x, 表示在区间 i ~ j 的左边放一个 x 能保证(i - 1, j) 的状态为必败态, r[i][j] 同理<p>
     * 证明该想法存在且唯一<p>
     * 唯一性证明：假设存在两个L1, L2 且L1 < L2, L1如果为必败态, 那么L2一定是必胜态,能从必胜太一定能够到达必败态,必败态唯一<p>
     * 存在的方式递推<p>
     * 假设 L [i ~ j - 1] R, 且 X = a[i], L 表示l[i][j - 1], R表示r[i][j - 1], 代表为定义<p>
     * 1、X == R, l[i][j] = 0, 显然成立, 因为已经是必败态, 不需要放<p>
     * 2、L < X, R < X, l[i][j] = X<p>
     * 因为r[i][j - 1]以及l[i][j - 1]的状态是必败态, 只要[i ~ j - 1]两侧最终有一个先到达 0,且另外一个就为y那就是必胜态,y < L, y < R,
     * 等价于你到一边取多少, 我只需要到另一边取相同的数, 就可以导致上述局面,所以l[i][j] = X为必败态<p>
     * 3、L > R, 且 R < X <= L, l[i][j] = X - 1<p>
     * ① 将右边拿到 < R, 那么左边拿到和对面一样就好了,参照 原则2<p>
     * ② 将右边拿到 = R, 那么左边全部拿完, 参照 原则1<p>
     * ③ 那么最优的一定是右边拿到 > R, 那么右边拿多少, 左边就拿多少就好, 或者是左边拿多少右边就拿多少, 因为右边一定会先到达 R, 所以满足<p>
     * 4、R < L, 且 L <= X < R, l[i][j] = X + 1<p>
     * 理由参照对称原则 3<p>
     * 5、X > L, X > R, l[i][j] = X<p>
     * 因为先手拿一边, 另外一边按照 原则 1, 2, 3, 4取, 如果说去完之后还是满足原则5, 那就取同样的即可<p>
     * 最后判定只需要判断l[2][n] != a[1], 相等就是必败态了
     */
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 1010;
    static int[][] l = new int[N][N], r = new int[N][N];
    static int[] a = new int[N];
    static int n;

    public static void main(String[] args) {
        int T = sc.nextInt();
        while (T-- > 0) {
            n = sc.nextInt();
            for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
            // 区间DP
            for (int len = 1; len <= n; len++) {
                for (int i = 1; i + len - 1 <= n; i++) {
                    int j = i + len - 1;
                    if (len == 1) l[i][j] = r[i][j] = a[i];
                    else {
                        int L = l[i][j - 1], R = r[i][j - 1], X = a[j];
                        if (X == R) l[i][j] = 0;
                        else if (L < X && R < X || L > X && R > X) l[i][j] = X;
                        else if (L > R) l[i][j] = X - 1;
                        else l[i][j] = X + 1;
                        // 对称原则
                        L = l[i + 1][j];
                        R = r[i + 1][j];
                        X = a[i];
                        if (L == X) r[i][j] = 0;
                        else if (L < X && R < X || L > X && R > X) r[i][j] = X;
                        else if (R > L) r[i][j] = X - 1;
                        else r[i][j] = X + 1;
                    }
                }
            }
            if (n == 1) out.println(1);
            else out.printf("%d\n", l[2][n] != a[1] ? 1 : 0);
        }
        out.flush();
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}